#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//1视为两段0的叠加，拆分开得到若干段，k = 各段长度的最大公因数

int main()
{
    int t = 0;
    scanf("%d", &t);
    while(t--)
    {
        int n = 0;
        scanf("%d", &n);
        char str[n + 1];
        scanf("%s", str);

        //不考虑边界1
        int pre = 0;
        int aft = n - 1;
        while(str[pre] == '1'){pre++;}
        while(str[aft] == '1'){aft--;}

        int k = 0;
        int ret[n + 1];//各段长度
        memset(ret, 0, sizeof(ret));

        int flag = 0;
        int count1 = 0;
        int count2 = 0;
        for(int i = pre; i <= aft; i++)
        {
            if(i > pre && str[i] != str[i - 1])
            {
                k++;
            }
            ret[k]++;
            ret[k + 1]++;
        }

        int min1 = ret[1];//第一小
        int min2 = ret[1];//第二小
        for(int i = 2; i <= k; i++)
        {
            if(ret[i] < min1)
            {
                min2 = min1;
                min1 = ret[i];
            }
            else if(ret[i] < min2)
            {
                min2 = ret[i];
            }
        }

        //各段长度的最大公因数
        while(min1 != 0)
        {
            int tmp = min2 % min1;
            min2 = min1;
            min1 = tmp;
        }

        printf("%d\n", min2);
    }
    return 0;
}